package leetcode_1000;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 周杨
 * 2018年11月18日 上午12:18:42 判断一个数组里的元素能否被分成若干个长度相同的数组 数组里的元素都是一致的
 * XOfAKindInADeckOfCards_914.java
 * description:用gcd算法实现 AC 43%
 */
public class XOfAKindInADeckOfCards_914 {
	public boolean hasGroupsSizeX(int[] deck) {
		Map<Integer,Integer> counts=new HashMap<Integer,Integer>();
		for(int i:deck) {
			counts.put(i, counts.getOrDefault(i, 0)+1);
		}
		int div=-1;//最小公约数
		for(int i:counts.values()) {
			if(div==-1)
				div=i;
			else {
				div=gcd(div,i);
			}
		}
		return div>=2;
    }
	
	public int gcd(int x, int y) {//最小公约数
        return x == 0 ? y : gcd(y%x, x);
    }
}
